\documentclass[11pt]{report}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{geometry} 
\usepackage{verbatim} 
\usepackage{amsmath,amsfonts,amssymb,amscd,amsthm,xspace}
\usepackage[ngerman]{babel}
\usepackage{amssymb}
\usepackage{paralist}

\newtheorem{satz}{Satz}
\newtheorem{korollar}{Korollar}
\newtheorem{lemma}{Lemma}
\newtheorem{bemerkung}{Bemerkung}
\newtheorem{beh}{Behauptung}
\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{tikz}
\usepackage{mathcomp}

% under and oversets
\newcommand{\Os}[2]{\overset{#1}{#2}}
\newcommand{\Us}[2]{\underset{#1}{#2}}
\newcommand{\OS}[2]{\Os{#1}{\overbrace{#2}}}
\newcommand{\US}[2]{\Us{#1}{\underbrace{#2}}}
% logic
\newcommand{\lfollow}{\rightarrow} % logical follow
\newcommand{\sfollow}{\Longrightarrow} % semantic follow

\newcommand{\case}[1]{\medskip \quad Fall #1 :\\\\}

\geometry{a4paper, left=2cm,right=2cm,top=2cm,bottom=2cm}
\parindent0.0em
\title{{\Huge Höhere Algroithmik II} \\ \vspace{1cm} {\Small Vorlesung von Prof. Helmut Alt, FU Berlin, Sommersemester 2011}}
\author{Eine Mitschrift der Studierenden}
\date{\today}
\begin{document}
%\maketitle

\section*{Graphenf\"arbung}

\subsection*{Definitionen}
sei im folgenden 
\begin{itemize}
\item[]$G =(V,E)$ ein ungerichteter Graph

\item[] $c : V \rightarrow \mathbb{N}$ F\"arbung \\
mit ${v,u} \in E \sfollow c(c) \neq c(v)$

\item[] $\chi(G)$ minimale Anzahl von Farben mit denen $G$ gef\"arbt werden kann.
$\chi(G)$ wird die Chromatische Zahl von $G$ genannt. \\
Wenn es eine Clique der Gr\"o"se $k$ in $G$ gibt, dann ist $\chi(G) \geq k$.

\item[] $\Delta(G)$ = maximaler Grad eines Knoten in $G$
\item[] $\Gamma(v)$ =  $\{u | \{v,u\} \in E\}$ Menge aller Nachbarn.
\end{itemize}

\subsection*{Probleme}
\begin{itemize}
\item[MINF\"ARB]: \\
\underline{gegeben}: Graph $G=(V,E)$ \\
\underline{gesucht}: F\"arbung von $G$ mit Anzahl der Farben = $\chi(G)$.

\item[F\"ARB]: \\
\underline{gegeben}: Graph $G=(V,E)$, $k \in \mathbb{N}$ \\
\underline{Frage}: ist $\chi(G) \leq k$?

\item[3F\"ARB]: \\
\underline{gegeben}: Graph $G = (V,E)$ \\
\underline{Frage}: ist $\chi(G) \leq 3$ ?
\end{itemize}

offensichtlich ist 3F\"ARB $\subset$ F\"ARB.

\begin{satz} $ $\\
3F\"ARB ist NP-vollst\"andig
\end{satz}

\begin{korollar} $ $
\begin{enumerate}[a)]
\item F\"ARB ist NP-vollst\"anding
\item MINF\"ARB ist NP-schwer
\end{enumerate}
\end{korollar}

\begin{bemerkung} $ $\\
2F\"ARB $\in$ $P$
\end{bemerkung}

\begin{proof} (Satz), 3F\"ARB \\
Ein Zeuge ist eine F\"arbung mit 3 Farben. Die \"Uberpr\"ufung ob eine solche F\"arbung korrekt ist,
ist in poly. Zeit m\"oglich. $\sfollow$ 3F\"ARB $\in$ NP.

\subsection*{Wir zeigen, 3SAT $\leq_p$ 3F\"ARB} $ $\\
Betrachten wir eine Formal $\phi$ von 3SAT, daher \\
$\phi$ ist eine Boolsche Formel in 3KNF mit \\
Variablen $x_1 \cdots x_n$ \\
Klauseln $\kappa_1 \cdots \kappa_k$
\medskip

\paragraph{Konstruktion des Graphen $G_{\phi}$} Der Graph $G_{\phi}$ besteht aus Teilgraphen $G_0, G_1, \cdots G_m$, die wie folgt definiert sind.

\begin{tikzpicture}
    \tikzstyle{var}=[draw,circle,fill=black,minimum size=3pt,
                            inner sep=0pt]
    
\begin{scope}    
    \draw (0,0) 		node [var] (x1) [label=left:$x_1$] {};
    \draw (0,-0.5) 	node [var] (x2) {};
    \draw (0,-2.5) 	node [var](xn1) {};
    \draw (0,-3) 		node [var](xn) [label=left:$x_n$] {};
    
    \draw (2,0) 		node [var] (nx1) [label=right:$\overline{x_1}$] {};
    \draw (2,-0.5) 	node [var] (nx2) [label=right:$\overline{x_2}$]{};
    \draw (2,-2.5) 	node [var] (nxn1) {};
    \draw (2,-3) 		node [var] (nxn) [label=right:$\overline{x_n}$] {};
    
    \draw (1,-4) 		node [var] (u) [label=right:$u$] {};
    
    \path (x2) -- (xn1) node [midway] {$\vdots$};
    \path (nx2) -- (nxn1) node [midway] {$\vdots$};
    
    \draw (x1) -- (u);
    \draw (x2) -- (u);
    \draw (xn1) -- (u);
    \draw (xn) -- (u);
    \draw (nx1) -- (u);
    \draw (nx2) -- (u);
    \draw (nxn1) -- (u);
    \draw (nxn) -- (u);

    \draw (1,-5) node (G0) {$G_0$};
\end{scope}

\begin{scope}[xshift=7cm]

    \draw (0,0) 		node [var] (ci) [label=left:$c_i$] {};
    \draw (0,-1) 		node [var] (bi) [label=left:$b_i$] {};
    \draw (0,-2) 		node [var] (ai) [label=left:$a_i$] {};
    
    \draw (2,-0.5) 	node [var] (zi) [label=right:$z_i$] {};
    \draw (2,-1.5) 	node [var] (yi) [label=right:$y_i$] {};
    
    \draw (4,-1) 		node [var] (v) [label=right:$v$; dieses $v$ ist f\"ur alle $G_i$ das gleiche] {};
    
    \draw (ci) -- (bi);
    \draw (ci) -- (zi); \draw (bi) -- (yi); \draw (ai) -- (zi); \draw (ai) -- (yi);
    \draw (zi) -- (v); \draw (yi) -- (v);
    
    \draw (2,-3) node (Gi) {$G_i, i = 1 \cdots k$};
\end{scope}

\begin{scope}
    \draw (v) to [out=-45,in=-90,color=red] (u) node [midway,color=gray] {existiert nur ein mal};
\end{scope}
    
\end{tikzpicture}

Weiterhin erzeugen wir f\"ur jede Klausel $\kappa_i = (\alpha_i, \beta_i, \gamma_i) \in \phi$ drei Kanten
$(\alpha_i, a_i)$, $(\beta_i, b_i)$, $(\gamma_i, c_i)$ wobei $a_i,b_i,c_i \in G_i$ und $\alpha_i, \beta_i, \gamma_i \in G_0$.

\begin{tikzpicture}
    \tikzstyle{var}=[draw,circle,fill=black,minimum size=3pt,
                            inner sep=0pt]
    
\begin{scope}    
    \draw (0,0) 		node [var] (x1) [label=left:$x_1$] {};
    \draw (0,-0.5) 	node [var] (x2) {};
    \draw (0,-2.5) 	node [var](xn1) {};
    \draw (0,-3) 		node [var](xn) [label=left:$x_n$] {};
    
    \draw (2,0) 		node [var] (nx1) [label=right:$\overline{x_1}$] {};
    \draw (2,-0.5) 	node [var] (nx2) [label=right:$\overline{x_2}$]{};
    \draw (2,-1) 		node [var] (nx3) [label=right:$\overline{x_3}$]{};
    \draw (2,-1.5) 	node [var] (nx4) [label=right:$\overline{x_4}$]{};
    \draw (2,-2.5) 	node [var] (nxn1) {};
    \draw (2,-3) 		node [var] (nxn) [label=right:$\overline{x_n}$] {};
    
    \draw (1,-4) 		node [var] (u) [label=right:$u$] {};
    
    \path (x2) -- (xn1) node [midway] {$\vdots$};
    \path (nx4) -- (nxn1) node [midway] {$\vdots$};
    
    \draw (x1) -- (u);
    \draw (x2) -- (u);
    \draw (xn1) -- (u);
    \draw (xn) -- (u);
    \draw (nx1) -- (u);
    \draw (nx2) -- (u);
    \draw (nxn1) -- (u);
    \draw (nxn) -- (u);

    \draw (1,-5) node (G0) {$G_0$};
\end{scope}

\begin{scope}[xshift=7cm]

    \draw (0,0) 		node [var] (ci) [label=left:$c_i$] {};
    \draw (0,-1) 		node [var] (bi) [label=left:$b_i$] {};
    \draw (0,-2) 		node [var] (ai) [label=left:$a_i$] {};
    
    \draw (2,-0.5) 	node [var] (zi) [label=right:$z_i$] {};
    \draw (2,-1.5) 	node [var] (yi) [label=right:$y_i$] {};
    
    \draw (4,-1) 		node [var] (v) [label=right:$v$] {};
    
    \draw (ci) -- (bi);
    \draw (ci) -- (zi); \draw (bi) -- (yi); \draw (ai) -- (zi); \draw (ai) -- (yi);
    \draw (zi) -- (v); \draw (yi) -- (v);
    
    \draw (2,-3) node (Gi) {$G_i, i = 1 \cdots k$};
\end{scope}

\begin{scope}
    \draw (v) to [out=-45,in=-90] (u) node [midway,color=gray] {};
    \draw (nx4) to [out=30, in=90,color=red] (ci) node [midway,color=gray] {falls $\overline{x_4}$ 3. Element der Klausel $\kappa_i$};
\end{scope}
    
\end{tikzpicture}

Zum Beispiel, wenn $\kappa_3 = (x_1, x_2, \overline{x_4})$, erzeugen wir die Kanten $(x_1, a_3), (x_2, b_3), (\overline{x_4}, c_3))$.

\begin{beh}
$\phi$ erf\"ullbar $\iff$ $G_{\phi}$ ist 3-f\"arbbar.
\end{beh}
\begin{proof} (Behauptung), $"\Rightarrow"$ \\
Sei $\phi$ erf\"ullbar. Dann f\"arben wir $G_{\phi}$ mit den Farben $\{0,1,2\}$ wie folgt: \\
Wir betrachten erf\"ullende Belegung und f\"arben in $G_0$ $x_1, \cdots, x_n, \overline{x_1}, \cdots, \overline{x_n}$ entsprechend der Belegung mit $0$
oder $1$ und $u$ mit $2$.

\begin{beh}
f\"ur $i = 1 \cdots k$ gilt: \\
falls eines der Literale $\alpha_i, \beta_i, \gamma_i$ mit 1 gef\"arbt ist, so kann $G_i$ mit 3 Farben gef\"arbt werden.
\end{beh}

\begin{proof}(Behauptung) \\
Wir setzen $c(v) = 0$. Zu beachten ist: $v$ ist mit $u$ verbunden und $c(u)=2$, damit ist diese Wahl zul\"assig.

\case{$c(\alpha_i) = 1$, so f\"arben wir $G_i$ wie folgt} 

\begin{tikzpicture}
    \tikzstyle{var}=[draw,circle,fill=white,minimum size=12pt,
                            inner sep=0pt]
\begin{scope}[xshift=1.5cm,yshift=-1.5cm]                    
    \draw (0,-0.6) 		node [var] (ai) [label=left:$a_i$] {0};
    \draw (1.7,0)	 		node [var] (zi) [label=right:$z_i$] {1};
    \draw (3,-1.5) 		node [var] (ci) [label=right:$c_i$] {2};
    \draw (1.7,-3) 		node [var] (bi) [label=right:$b_i$] {};
    \draw (0,-2.4) 		node [var] (yi) [label=left:$y_i$] {2};
    
    \draw (ai) -- (zi);
    \draw (zi) -- (ci);
    \draw (ci) -- (bi);
    \draw (bi) -- (yi);
    \draw (yi) -- (ai);
\end{scope}
\draw (0,0) 		node [var] (lai) [label=left:$\alpha_i$] {1};
\draw (0,-3) 		node [var] (lbi) [label=left:$\beta_i$] {$\{0,1\}$};
\draw (0,-6) 		node [var] (lci) [label=left:$\gamma_i$] {$\{0,1\}$};
\draw (7,0) 		node [var] (v) [label=right:$v$] {0};

\draw (lai) to [out=0,in=90] (ai);
\draw (lbi) to [out=-90,in=180] (bi);
\draw (lci) to [out=0,in=-90] (ci);
\draw (zi) to [out=90,in=180] (v);
\draw (yi) to [out=0,in=180] (v);

\end{tikzpicture} \\
Wir setzen $b_i$ auf $\lnot \beta_i$. Damit ist diese
F\"arbung zul\"assig.

\case{$c(\alpha_i) = 0 \land c(\beta_i) = 1$, so f\"arben wir $G_i$ wie folgt} 

\begin{tikzpicture}
    \tikzstyle{var}=[draw,circle,fill=white,minimum size=12pt,
                            inner sep=0pt]
\begin{scope}[xshift=1.5cm,yshift=-1.5cm]                    
    \draw (0,-0.6) 		node [var] (ai) [label=left:$a_i$] {2};
    \draw (1.7,0)	 		node [var] (zi) [label=right:$z_i$] {1};
    \draw (3,-1.5) 		node [var] (ci) [label=right:$c_i$] {2};
    \draw (1.7,-3) 		node [var] (bi) [label=right:$b_i$] {0};
    \draw (0,-2.4) 		node [var] (yi) [label=left:$y_i$] {1};
    
    \draw (ai) -- (zi);
    \draw (zi) -- (ci);
    \draw (ci) -- (bi);
    \draw (bi) -- (yi);
    \draw (yi) -- (ai);
\end{scope}
\draw (0,0) 		node [var] (lai) [label=left:$\alpha_i$] {0};
\draw (0,-3) 		node [var] (lbi) [label=left:$\beta_i$] {1};
\draw (0,-6) 		node [var] (lci) [label=left:$\gamma_i$] {$\{0,1\}$};
\draw (7,0) 		node [var] (v) [label=right:$v$] {0};

\draw (lai) to [out=0,in=90] (ai);
\draw (lbi) to [out=-90,in=180] (bi);
\draw (lci) to [out=0,in=-90] (ci);
\draw (zi) to [out=90,in=180] (v);
\draw (yi) to [out=0,in=180] (v);

\end{tikzpicture} \\

\case{$c(\alpha_i) = 0 \land c(\beta_i) = 0 \land c(\gamma_i) = 1$, so f\"arben wir $G_i$ wie folgt} 

\begin{tikzpicture}
    \tikzstyle{var}=[draw,circle,fill=white,minimum size=12pt,
                            inner sep=0pt]
\begin{scope}[xshift=1.5cm,yshift=-1.5cm]                    
    \draw (0,-0.6) 		node [var] (ai) [label=left:$a_i$] {2};
    \draw (1.7,0)	 		node [var] (zi) [label=right:$z_i$] {1};
    \draw (3,-1.5) 		node [var] (ci) [label=right:$c_i$] {0};
    \draw (1.7,-3) 		node [var] (bi) [label=right:$b_i$] {2};
    \draw (0,-2.4) 		node [var] (yi) [label=left:$y_i$] {1};
    
    \draw (ai) -- (zi);
    \draw (zi) -- (ci);
    \draw (ci) -- (bi);
    \draw (bi) -- (yi);
    \draw (yi) -- (ai);
\end{scope}
\draw (0,0) 		node [var] (lai) [label=left:$\alpha_i$] {0};
\draw (0,-3) 		node [var] (lbi) [label=left:$\beta_i$] {0};
\draw (0,-6) 		node [var] (lci) [label=left:$\gamma_i$] {1};
\draw (7,0) 		node [var] (v) [label=right:$v$] {0};

\draw (lai) to [out=0,in=90] (ai);
\draw (lbi) to [out=-90,in=180] (bi);
\draw (lci) to [out=0,in=-90] (ci);
\draw (zi) to [out=90,in=180] (v);
\draw (yi) to [out=0,in=180] (v);

\end{tikzpicture}
\end{proof}

$\sfollow$ Wir k\"onnen den gesamten Graphen $G_{\phi}$ 3-f\"arben wenn $\phi$ erf\"ullbar ist.

\end{proof}
\begin{proof} (Behauptung), $"\Leftarrow"$ \\

\end{proof}
\end{proof}

\end{document}
